An identification scheme is a method by which a party A can prove to a party B that he is indeed A. In 1976 Diffie and Hellman (DH) introduced the idea of digital signatures. In 1978 Rivest, Shamir and Addleman (RSA) suggested an implementation of this idea based on the assumption that factoring large integers is a hard computational problem. However, there is no known proof that party B who is validating the identity of a using digital signatures cannot turn around falsely, and prove that he is A to a third party C, even under the assumption that factoring integers is a hard computational problem. Moreover, the cost of using the RSA digital signature scheme is about k modular multiplications each of cost k.sup.2 k digit numbers. The smallest value of k considered secure today is k =200. This makes using RSA for identification in software too slow, and in hardware and VLSI to expensive and special purpose.
In 1985 Goldwasser, Micali and Rackoff (GMR) presented the idea of "Zero-Knowledge Interactive Proof-Systems" which are interactive procedures by which a party A (the prover) can convince a party B (the verifier) that a theorem is true without telling B anything else. One possible theorem would be that A knows how to perform a hard computation. If the ability to perform this computation identifies A, an interactive identification scheme immediately follows.
In 1986 Goldreich, Micali and Wigderson (GMW) showed that if one-way functions exist then every language in nondeterministic polynomial time (NP) has a computationally zero-knowledge interactive proof system. Although theoretically quite exciting, using their result in practice would be very inefficient.
In 1986 Shamir and Fiat (FS) suggested a particular zero-knowledge identification scheme based on the assumption that distinguishing quadratic residues from non-residues modulo composite integers is a hard problem. A number of modular multiplication of many-digit numbers are required.
An example of a zero knowledge identification scheme based on the ideas of GMW and Blum is illustrated in FIG. 1. In that system, a prover A must prove its identification to a verifier B. The prover A may, for example, be a smart card having a processor thereon and the verifier B may be an automatic teller machine. Other forms of the prover A include credit cards, access control cards and digital passports. The prover A carries an identification set of information S.sub.i which is unique to prover A and which is also known to verifier B. Knowledge of that identification set of information, however, is not considered sufficient to identify prover A, because it is generally available at least to verifiers and an eavesdropper from a prior identification may also have that identification set. To prove its identity, prover A must prove that it also has access to a solution subset S.sub.s without actually disclosing that solution subset to either the verifier B or a potential eavesdropper. This result is accomplished by means of a zero knowledge system.
The solution subset should have a predetermined mathematical relationship with the identification set and be readily verifiable as a proper solution, but it should not be readily determinable from the identification set. For example, as illustrated in FIG. 1B, the identification set could be the graph illustrated. The solution subset could be the listing of vertices which identify a Hamiltonian cycle; that is, a cycle such as shown in bold lines which intersects each vertex without overlap. The graph of FIG. 1B is very simple for purposes of illustration. With more complex graphs, a Hamiltonian cycle may be nearly impossible to determine from the full graph. On the other hand, by starting with a Hamiltonian cycle, one can develop a complex graph which includes the cycle so that prover A could be provided with both the complex graph as the identification set S.sub.i and the Hamiltonian cycle as the solution subset S.sub.s. The cycle and graph would be generated by the prover itself or by a trusted center.
Given that prover A has access to both the identification set and the solution subset, and that the verifier B only has access to the identification set, the task remains for prover A to prove to the verifier B that it in fact has access to the solution set without actually reealing the solution set to verifier B. To that end, the prover has a permutator .pi., an encryptor E and a decryptor. Based on a random sequence, the vertices of the identification set graph can be permutated for successive message transmissions to the verifier. Thus, the permutated graph S.sub..pi.i shown in FIG. 1B is the initial identification graph with the vertices renumbered according to some random process. Prover A then encrypts the individual elements of the permutated identification set of information for transfer as S.sub.i.pi.E to the verifier B. Also, the permutation .pi. is encrypted for transfer to verifier B. As illustrated in FIG. 1C, this encryption is analagous to the placement of each vertex of the permutated identification set in a respective envelope for transfer to verifier B. Such a transfer is a commitment by prover A to the permutated graph as well as to the permutation which allows for reconstruction of the original graph S.sub.i ; however, the encryption "envelopes" cannot then be opened by the verifier B.
Next, the verifier randomly selects, for each of successive encrypted permutated graphs, either the entire identification set or the solution subset. In response to that random selection, the prover A either opens all encryption envelopes or only those envelopes corresponding to the solution subset. If all envelopes are opened by transferring the original nonencrypted permutated identification set S.sub..pi.i and the nonencrypted permutation .pi., the verifier B can reconstruct S.sub.i and compare the reconstructed set to the already available identification set S.sub.i. This proves that A had in fact committed to a permutation of the identification set. As already noted, if this were the only test, there would be no verification because others might have access to that identification set. However, the verifier may at random select the solution subset. In that case, the prover A returns only the nonencrypted permutated vertices of the Hamiltonian cycle. For example, the Hamiltonian cycle illustrated in FIG. 1B would be returned to the verifier as follows: (1,2), (2,3), (7,3), (7,4), (4,5), (5,6) and (1,6). Because the information is permutated and the permutation .pi. is not in this case available to B, B cannot make a correspondence between the permutated Hamiltonian cycle and the original nonpermutated cycle S.sub.i and thus gain knowledge of the Hamiltonian cycle corresponding to S.sub.i. However, B could step through the vertices to confirm that the permutated vertices in fact create a cycle naming each of the seven vertices without overlap.
For a full commitment by A, the prover A must encrypt the information in a manner which cannot readily be decrypted by the verifier or an eavesdropper; yet the encryption method must allow the verifier to readily confirm that, when provided with both the encrypted information and the nonencrypted information, one is the true encryption of the other. For example, in using for encryption the RSA function m.sup.3 mod n where m is the transferred message and n is a multidigit product of two primes, the verifier could not readily decrypt the information. However, with the nonencrypted information later provided with selection of all vertices and the permutation, the verifier could itself easily encrypt the information and compare it to the encrypted information to which the prover had already committed itself.
Thus, because the prover A had committed to the full set of vertices, it must know both the identification set and the solution subset in order to be correct with either selection made by the verifier. For any one transfer of a permutated graph, the prover A could transfer either the proper graph with an incorrect solution or the proper solution with an incorrect graph. However, it could not transfer both a correct graph and a correct a cycle without access to the solution. With one transfer of the permutated graph, the verifier could only verify to fifty percent probability; however, with successive transfers of the permutation graph and random selections, the verifiction becomes more and more certain. If the prover does not have both the identification set and the solution set, the verifier would soon select an incorrect full graph or an incorrect cycle from the prover.
Previous methods of commitment such as that just described are based on the assumption that one-way functions, such as the RSA function, exist. This assumption has not yet been proven. Further, the many modular multiplications of large digit numbers required for secure use of the RSA and other functions make those functions too slow for software and too expensive for hardware. Further, the approaches lose security when performed in parallel, that is, when multiple permutated graphs are transferred to the verifier in parallel.